The present invention relates to a disk drive controller that provides for the handling of queued commands from a host device and in particular to a method for detecting a command conflict that would restrict reordering of queued commands.
FIG. 1 illustrates a conventional interface 100 for exchanging data between a hard disk drive 120 and a host 110. The host 110 is typically a computer such as a personal computer, server or workstation. The disk drive 120 typically provides mass data storage for the computer. The disk drive 120 comprises a head disk assembly (HDA) 130 and an integrated controller 140. The head disk assembly 130 includes one or more storage disks 132. The controller 140 is hardware and associated firmware that interfaces to the host 110 and controls the transfer of data between the disk drive and the controller""s data buffer or cache (not shown). The host 110 and disk drive 120 are connected by a bus 112, which provides a standard physical and data link layer between the host 110 and controller 140. Associated protocols provide a standard communications link layer between the host 110 and controller 140. The most common standards for these physical, data and communications layers of the host-controller interface 100 are SCSI and ATA. One ATA standard, described in ANSI document number NCITS 317-1998 entitled xe2x80x9cAT Attachment with Packet Interface Extension (ATA/ATAPI-4),xe2x80x9d commonly known as ATA-4, defines a protocol for queued host commands.
Command queuing is an optional command scheme whereby the host 110 sends multiple tagged commands for processing by the controller 140. The tagged commands are stored in a command queue, to be executed sequentially. Potentially, these commands can be reordered by the controller""s microprocessor into an optimal execution sequence for enhanced disk drive performance, as described below. Command queuing also reduces interface bus overhead because the controller 140 can perform disk accesses while waiting for the next host command. Further, command queuing allows the controller 140 to release the interface bus 112 if command execution will be delayed.
Command reordering is a technique used with command queuing to mitigate the effects of seek time and rotational latency, the slowest aspects of disk drive data transfers. If the command order can be changed so that commands accessing data in areas closer to the head are given greater priority, then the performance of the drive improves. For example, if a first command received from the host requests data from an inner track, a second command requests data from an outer track and a third command requests data, also from an inner track, the head has to travel from the inner tracks to the outer tracks, and then back to the inner tracks to execute the commands in chronological order. Command reordering would efficiently execute the first and third commands sequentially.
FIG. 2 illustrates the taskfile register content for queued commands, as defined in the ATA-4 specification. The taskfile register 200 is a memory located on the controller 140 (FIG. 1) at specific host I/O addresses. The host writes to the taskfile register 200 to initiate commands, and the host reads the taskfile register to obtain data transfer status (not shown). For a queued read or write command, the taskfile register 200 contains a block count 210, a tag 220, a logical block address (LBA) 230 and a command code 240. The LBA 230 specifies the logical starting address on the storage disks 132 (FIG. 1) for a read or write. The block count 210 specifies the number of blocks of data to transfer between the storage disks 132 (FIG. 1) and the host 110 (FIG. 1). The tag 220 is a host designated command identifier, allowing the host 110 (FIG. 1) to determine which of several queued and possibly reordered commands was subsequently executed by the controller 140 (FIG. 1). The command code 240 is a unique bit pattern that specifies a particular host command.
A problem that arises with respect to queued commands and, in particular, with command reordering is that a conflict can exist when the address range of a write command overlaps with the range of a previously queued read or write command. FIG. 3A illustrates one such conflict between two write commands 310, 320. For example, assume a first queued write command 310 has an address range extending from 100 to 199, as shown. Assume a second queued write command 320 is received with an address range extending from 45 to 119, as shown. The host would assume that these commands 310, 320 are executed chronologically, with the overlapping data portion 322 of the second write command 320 overwriting the data portion 312 of the first write command 310 in the address range from 100 to 119. If the controller reorders these queued commands 310, 320, then the overlapping data portion 312 of the first write command 310 would, instead, overwrite the data portion 322 of the second write command 320. A subsequent disk read in the address range of 100 to 119 would return erroneous results to the host.
FIG. 3B illustrates a conflict between a queued read command 330 and a subsequent queued write command 340. For example, assume the queued read command 330 has an address range extending from 100 to 199, as shown. Assume the subsequent queued write command 340 has an address range extending from 170 to 244, as shown. The host would assume that these commands 330, 340 are executed chronologically, with the read command returning data from the address range 170 to 199 prior to being overwritten by the write command 340. If the controller reorders these queued commands 330, 340, then the overlapping data portion 342 of the write command 340 would, instead, overwrite the data portion 332 subsequently accessed by the read command 330, returning erroneous data to the host.
A read command overlapping with another read command is not a conflict, because correct data is returned to the host regardless of the order of execution of read commands. Further, a subsequent read command overlapping with a previous write command is not a conflict. The data for the queued write would be held in the controller""s cache. If the read command is reordered to occur before the write command, the overlapping portion of the read command would be provided from the cache rather than from the storage disks. Thus, the data returned to the host from the overlapping portion of the read command would be the same regardless of the order of command execution.
One aspect of the present invention is a conflict detection method for a disk drive controller, such a conflict potentially occurring if the execution sequence of queued commands sent from a host is reordered to optimize disk drive data transfers. The conflict detection method comprises the steps of decoding a first command, where the first command is a queued read or a write, and reading an associated first logical block address (LBA) and first block count, where the first LBA and the first block count define a first address range. The method further comprises the steps of decoding a second command, where the second command is a write, and reading an associated second LBA and a second block count, where the second LBA and the second block count define a second address range. The method also comprises the steps of detecting an overlap between the first address range and the second address range and setting a conflict flag based on the overlap. In addition the method comprises the step of restricting command reordering based upon the flag in order to prevent the conflict from occurring.
In one embodiment, the conflict detection method described in the previous paragraph further comprises the steps of reading a tag value associated with the first command, creating an entry in random access memory (RAM) according to the tag value, and storing the first LBA and the first block count in the entry, wherein the setting step comprises the substep of storing a set bit in the entry corresponding to the conflict flag. The method may also comprise the steps of unloading the first command in chronological order from a first-in-first-out (FIFO) memory and reading the set bit from the RAM entry, wherein the restricting step comprises the substep of processing the first command before any subsequent commands in the FIFO. In another embodiment, the conflict detection method further comprises the steps of reading a tag value associated with the second command, creating an entry in random access memory (RAM) according to the tag value, and storing the second LBA and the second block count in the entry, wherein the setting step comprises the substep of storing the conflict flag in the entry. In yet another embodiment, the conflict detection method further comprises the steps of reading a tag value associated with the first command, creating an entry in random access memory (RAM) according to the tag value, and storing the first LBA and the first block count in the entry, wherein the detecting step comprises the substeps of reading the first LBA and the first block count from the entry and comparing the first LBA and the first block count with the second LBA and the second block count. In another embodiment, the conflict detection method further comprises the steps of reading a first tag value associated with the first command, creating an entry in random access memory (RAM) according to the tag value, the entry having a valid flag field. The method also comprises the steps of reading a second tag value associated with the second command, accessing the RAM according to the second tag value, and indicating an error if the accessing step reads the entry and the valid flag is set. In a further embodiment, the conflict detection method also comprises the step of clearing the conflict flag upon completion of the first command.
The invention can also be viewed as a disk drive controller for processing host commands, each having an address range, which are received in a first order from a host and queued for subsequent execution, wherein the queued commands can be executed in a second order for improved latency. The disk drive controller comprises a command queue memory for storing a first one and a second one of the received host commands which are queued for execution, the second one of the host commands being a write command. The controller further comprises a scan engine, for scanning the command queue memory to detect an overlap between the address range of the first command and the address range of the second command; a means, responsive to the scan engine scanning the command queue memory, for setting a conflict flag; and a means, responsive to the setting of the conflict flag, for modifying the second order of execution to avoid a conflict from the second command.